/*
 * Mini-language
 * CS550
 * 4/21/2011
 *
 * Aaron Chapin
 * Matthew Patchin
 * Jordan Santell
 * Bo Yan
 *
 * Original created by Mike Kopack, 2009
  */


import java.util.*;

class Cell{
    int car, cdr;
    boolean isPointer, isMarked;
    
    public Cell(){
        car = cdr = 0;
        isPointer = isMarked = false;
        }
    
    public Cell(int newCar, int newCdr){
        car = newCar;
        cdr = newCdr;
    }
    
    public void print(){
        System.out.println(toString());
    }
    @Override
    public String toString(){
        if(isPointer)
            return "points to ["+car+"]";
        else
            return "Value is: "+car;
    
    }
}

class Heap_{

    int heapSize;
    Cell[] cells;
    int[] available; //maybe should be arraylist
    int availableCell = 0;
    HashMap<String, Element> newTable;
    //int numAvailable //maybe
    public Heap_(int size, HashMap<String, Element> table){
        heapSize = size;
        newTable = table;
        cells = new Cell[heapSize];
        available = new int[heapSize];
        
        //initializes the cells in Cells and populate availability array
        //cell[i] car will = 0 to begin and its cdr will point ot the next cell
        //available[i] will simply have i, meaning that cell is available
        //maybe arraylist would be better for this?
        for(int i = 0; i < heapSize-1; i++){
            cells[i] = new Cell(0, i+1);
            available[i] = i;
        }
        cells[heapSize-1] = new Cell(0,-1);
    }//end Heap_ constructor
    
    public void print(){
        System.out.print("Heap car:[ ");
        for (int i = 0; i < heapSize; i++){
            System.out.print(cells[i].car+" ");
        }
        System.out.println("]");
        System.out.print("Heap cdr:[ ");
        for (int j = 0; j < heapSize; j++){
            System.out.print(cells[j].cdr+" ");
        }
        System.out.println("]");
    }
    
    public void updateAvailable(){
        availableCell = cells[availableCell].cdr;
    }
    
    public int insertValue(Element e, int newCdr){
        //need s check for available space
        //System.out.println("hgeljkhseg");
        int index = availableCell;
        System.out.println(e.toString());
        updateAvailable();
        
        cells[index].car = e.value();
            
        cells[index].cdr = newCdr;
        
        cells[index].isMarked = false;
        
        if(e.isList)
        cells[index].isPointer = true;
        else
        cells[index].isPointer = false;
        //System.out.println("after insert");
        //print();
        return index;
    
    }
    //insertEmptyList ??
    
    public void markAndSweep(){
        for (String name : newTable.keySet()) {
            if(newTable.get(name).isList)
                mark(newTable.get(name).val);
        }
    
    
    
    }//end markandsweep
    
    public void mark(int index){
        cells[index].isMarked = true;
        //if its pointing, car will point to the start of the sublist
        if(cells[index].isPointer == true)
            mark(cells[index].car);
        //if its just a number the cdr will point to the next element
        if(cells[index].cdr != -1)
            mark(cells[index].cdr);
        sweep();
        unMark();
    }//end mark
    
    public void unMark(){
        for(int i = 0; i< heapSize; i++)
            cells[i].isMarked = false;
    }//end unmark
    
    public void sweep(){
        for(int i = 0; i < heapSize; i++){
            
            if(cells[i].isMarked == false){
                cells[i].car = 0;
                cells[i].cdr = availableCell;
                
                cells[i].isMarked = false;
                cells[i].isPointer = false;
                availableCell = i;
            }//end if
                
            
        }//end for
    }//end sweep
}//end heap_


class Expr {

    public Expr() {
    }

    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        return new Element(0);
    }
}


/*
class Sequence{

    ArrayList<Expr> listElements;
    Element first = new Element(0, "Integer");

    public Sequence(){
        listElements = new ArrayList<Expr>();
    }
    
    public void insertListElement (Expr listElement){
        listElements.add(listElement);
    }

    public void insertListElement (int placement, Expr listElement){
        listElements.add(placement,listElement);
    }
    
    public void print(){
        System.out.println(toString());
    }

    public void appendSequence(Sequence otherseq)
    {
        for(int i = 0; i < otherseq.listElements.size(); i++)
        {
            insertListElement(otherseq.listElements.get(i));
        }
    }


    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) 
    {
        for(int index = 0; index<listElements.size(); index++)
        {
              Element e = listElements.get(index).eval(nametable,functiontable,var, h);
            listElements.set(index,e);
            if(index < 1)
                first = e;
        }                
    }

    @Override
    public String toString()
    {
        int size = listElements.size();
        String out = "";
        for(int i = 0; i < size; i++){
            out += listElements.get(i).toString();
            if(i != size-1)
                out +=", ";
        }
        return out;
    }
}
*/
class Element extends Expr{
       
    Integer val;
    List_ lst;
    boolean isList;
    Integer test = 111;
    
    public Element(int v){
        val =new Integer(v);
        isList = false;
    
        
    }
    
    public Element(Integer v){
        val = v;
        isList = false;
        
    }
    public Element (List_ l){
        lst = l;
        isList = true;
        
    }
    
    public int value(){
        
        return val;
    }
    
    public List_ getList(){
        return lst;
    }
    
        
    public void print(){
        if(isList)
            lst.print();
        else
            System.out.println(val.toString());
    }

    @Override
    public String toString()
    {
        if(isList)
            return lst.toString();
        else //if(!isList)
            return val.toString();
    }
}




class List_ extends Expr{
    
    //private List<Element> list;
    private Expr seq;
    private String ident;
    private Boolean evaled;
    
    public List_(){
        seq = new Expr();
        ident = null;
        evaled = false;
    }
    
    public List_(String ident)
    {
        seq = new Expr();
        this.ident = ident;
        evaled = false;
    }
    
    public void setSequence (Expr sequence){
        seq = sequence;
    }

    public Expr getSeq()
    {
        return seq;
    }
    
    public void print(){
        System.out.println(toString());
    }

    public Expr getSequence(){
        return seq;
    }
    
    //public int getListSize(){
    //    return seq.listElements.size();
    //}
/*
    public List_ concatList(List_ otherList)
    {
        Sequence newSeq = new Sequence();
        newSeq.appendSequence(this.seq);
        newSeq.appendSequence(otherList.getSeq());
        List_ newList = new List_();
        newList.setSequence(newSeq);
        return newList;
    }
    */
    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) 
    {
        if(!evaled)
        {
            evaled = true;
            if(ident != null)
            {
                if(nametable.get(ident).isList)
                {
                    seq = nametable.get(ident).getList().getSeq();    
                }else{
                    System.err.println("PASSED INVALID REFERENCE TO LIST");
                    System.exit(1);
                }
            }else{
                //if(this.getListSize()>0)
                    seq.eval(nametable, functiontable, var, h);
            }
        }
        return new Element(this);
    }

    @Override
    public String toString()
    {
        String out = "[";
        if(seq != null)
            out += seq.toString();
        out += "]";
        return out;
    }
}
/*
class Concat extends Expr{
        
    private Expr l1,l2;
    
    public Concat(Expr e1, Expr e2){
        l1 = e1;
        l2 = e2;
    }
    
    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h){
        
        List_ list1, list2;
        //They both need to be lists
        if(!l1.eval(nametable, functiontable, var, h).isList || !l2.eval(nametable, functiontable, var, h).isList){
            System.out.println("Concat: Both expressions must be lists");
            System.exit(1);
        }

        list1 = l1.eval(nametable, functiontable, var, h).getList();
        System.out.println("List1:"+list1.toString());
        list2 = l2.eval(nametable, functiontable, var, h).getList();
        System.out.println("List2:"+list2.toString());
            
        return new Element(list1.concatList(list2));
    }
}//end class Concat
    */
class Cons extends Expr{
    Expr e, L;
    int firstElement;
    boolean lastEle;
    
    public Cons(Expr e1, Expr L1){
        //System.out.println("dfhdfgh");
        e = e1;
        L = L1;
        lastEle = false;
    }
    
    public Cons(Expr e1){
        //System.out.println("jjjjjj");
        e = e1;
        L = null;
        lastEle = true;
        //System.out.println(e.toString());
    }
    
    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h){
        int address;
        
        //System.out.println("dgsg");
        
        //System.out.println("dataType = :"+L.eval(nametable, functiontable, var, h).datatype);
        //Element arg2 = L.eval(nametable, functiontable, var, h);
        
        if(L == null){
            //System.out.println("here");
            address = h.insertValue(e.eval(nametable, functiontable, var, h), -1);
            
        }
        else{
            //System.out.println("HERE");
            address = h.insertValue(e.eval(nametable, functiontable, var, h), L.eval(nametable, functiontable, var, h).value());
            
        }       
        firstElement = address;
        return new Element(address);
    
    }
    
    @Override
    public String toString()
    {
        
        return new Integer(firstElement).toString();
    }
    
    
}//end cons
/*        
class Car extends Expr{
    Expr e;
        
    public Car(Expr e1){
        e = e1;
    }
        

           public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h){
                        List_ list;
                        boolean isNum = false;
                        list = e.eval(nametable, functiontable, var, h).getList();
                        //list.print();
                        List_ finalList = new List_();
                        Sequence s = new Sequence();
                        Element d = list.getSequence().listElements.get(0).eval(nametable, functiontable, var,h);                
                        Integer numResult = new Integer(0);
                        s.insertListElement(list.getSequence().listElements.get(0));
                        String j = s.toString();
                                //System.out.println("String version:" + j);                
                         try{
                                numResult = new Integer(j);
                                isNum = true;
                                }
                                catch(Exception e){
                                
                                }
                        System.out.println("b:"+isNum);
                        if(isNum)
                            return new Element(numResult);                 
                        else{
                               finalList.setSequence(s);
                            return new Element(finalList);                          
                        }
                      
                                  }

    
    

}//end Car
        
class Cdr extends Expr{
            
    Expr e;
            
    public Cdr(Expr e1){
        e = e1;
    }
        
    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h){
        
          if(!e.eval(nametable, functiontable, var, h).isList)    {
              System.err.println("Cdr: Object not a list");
            System.exit(1);
        }
                
        List_ list = e.eval(nametable, functiontable, var, h).getList();
        List_ finalList = new List_();
        Sequence s = new Sequence();
        
        //in theory starts from second index in list(1) and puts all into the new list
        for(int i = 1; i < list.getListSize(); i++){
            s.insertListElement(list.getSequence().listElements.get(i));
        }
        finalList.setSequence(s);
        return new Element(finalList);
    }
}
    */        
/*
class Nullp extends Expr{
            
    Expr list;
            
    public Nullp(Expr e){
        list = e;
    }
            
    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h){
        if(!list.eval(nametable, functiontable, var, h).isList)    {
            System.err.println("Nullp: Object not a list");
            System.exit(1);
        }
        List_ l = list.eval(nametable, functiontable, var, h).getList();    
        if(l.getListSize()<=0)
            return new Element(1);
        else
            return new Element(0);
    }
}
    */    
class Intp extends Expr{
            
    Expr num;
            
    public Intp (Expr e){
        num = e;
    }
         
    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h){
        if(!num.eval(nametable, functiontable, var, h).isList)
            return new Element(1);
        else
            return new Element(0);
    }
}//end intp

        
class Listp extends Expr{
            
    Expr list;
            
    public Listp ( Expr e){
        list = e;
    }
        
    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h){
                
        if(list.eval(nametable, functiontable, var, h).isList)
            return new Element(1);
        else
            return new Element(0);
    }
}//end listp

    
    


class Ident extends Expr {

    private String name;

    public Ident(String s) {
        name = s;
    }

    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        return nametable.get(name);
    }
}

class Number extends Expr {

    private Integer value;

    public Number(int n) {
        value = new Integer(n);
    }

    public Number(Integer n) {
        value = n;
    }

    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        System.out.println("jgjkgh");
        return new Element(value);
    }
        
        @Override
        public String toString()
        {
            return value.toString();
        }
}

class Times extends Expr {

    private Expr expr1,  expr2;

    public Times(Expr op1, Expr op2) {
        expr1 = op1;
        expr2 = op2;
    }

    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        if(expr1.eval(nametable,functiontable,var,h).isList ||
            expr2.eval(nametable,functiontable,var,h).isList)    {
            System.err.println("Times: Both expressions must be integers");
            System.exit(1);
        }
      return new Element(expr1.eval(nametable, functiontable, var,h).value() * expr2.eval(nametable, functiontable, var,h).value());
    }
}

class Plus extends Expr {

    private Expr expr1,  expr2;

    public Plus(Expr op1, Expr op2) {
        expr1 = op1;
        expr2 = op2;
    }

    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        if(expr1.eval(nametable,functiontable,var,h).isList ||
            expr2.eval(nametable,functiontable,var,h).isList)    {
            System.err.println("Plus: Both expressions must be integers");
            System.exit(1);
        }
      return new Element(expr1.eval(nametable, functiontable, var,h).value() + expr2.eval(nametable, functiontable, var,h).value());
    }
}

class Minus extends Expr {

    private Expr expr1,  expr2;

    public Minus(Expr op1, Expr op2) {
        expr1 = op1;
        expr2 = op2;
    }

    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        if(expr1.eval(nametable,functiontable,var, h).isList ||
            expr2.eval(nametable,functiontable,var, h).isList)    {
            System.err.println("Minus: Both expressions must be integers");
            System.exit(1);
        }
      return new Element(expr1.eval(nametable, functiontable, var,h).value() - expr2.eval(nametable, functiontable, var,h).value());
    }
}

//added for 2c
class FunctionCall extends Expr {

    private String funcid;
    private ExpressionList explist;

    public FunctionCall(String id, ExpressionList el) {
        funcid = id;
        explist = el;
    }
   //debateable
    public Element eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        return new Element(functiontable.get(funcid).apply(nametable, functiontable, var, explist, h));
    }
}

abstract class Statement {

    public Statement() {
    }

    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) throws Exception {
    }
}

// added for 2c
class DefineStatement extends Statement {

    private String name;
    private Proc proc;
    private ParamList paramlist;
    private StatementList statementlist;

    public DefineStatement(String id, Proc process) {
        name = id;
        proc = process;
    }

    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functable, LinkedList var, Heap_ h) {
        // get the named proc object from the function table.
        //System.out.println("Adding Process:"+name+" to Functiontable");
        functable.put(name, proc);
    }
}

class ReturnStatement extends Statement {

    private Expr expr;

    public ReturnStatement(Expr e) {
        expr = e;
    }

    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) throws Exception {
        //Java can't throw exceptions of numbers, so we'll convert it to a string
        //and then on the other end we'll reconvert back to Integer..
        throw new Exception(Integer.toString(expr.eval(nametable, functiontable, var, h).value()));
    }
}

class AssignStatement extends Statement {

    private String name;
    private Expr expr;

    public AssignStatement(String id, Expr e) {
        name = id;
        expr = e;
    }

    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        /* add name to the statementlist of variable names */
        if (!var.contains(name)) {
            var.add(name);
        //insert the variable with the specified name into the table with the 
        // evaluated result (which must be an integer
        }
        nametable.put(name, expr.eval(nametable, functiontable, var,h));
    }
}

class IfStatement extends Statement {

    private Expr expr;
    private StatementList stmtlist1,  stmtlist2;

    public IfStatement(Expr e, StatementList list1, StatementList list2) {
        expr = e;
        stmtlist1 = list1;
        stmtlist2 = list2;
    }

    public IfStatement(Expr e, StatementList list) {
        expr = e;
        stmtlist1 = list;
    }

    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) throws Exception {
        if (expr.eval(nametable, functiontable, var,h).value() > 0) {
            stmtlist1.eval(nametable, functiontable, var, h);
        } else {
            stmtlist2.eval(nametable, functiontable, var, h);
        }
    }
}

class WhileStatement extends Statement {

    private Expr expr;
    private StatementList stmtlist;

    public WhileStatement(Expr e, StatementList list) {
        expr = e;
        stmtlist = list;
    }

    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) throws Exception {
        while (expr.eval(nametable, functiontable, var,h).value() > 0) {
            stmtlist.eval(nametable, functiontable, var,h);
        }
    }
}

class RepeatStatement extends Statement {

    private Expr expr;
    private StatementList sl;

    public RepeatStatement(StatementList list, Expr e) {
        expr = e;
        sl = list;
    }

    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) throws Exception {
        do {
            sl.eval(nametable, functiontable, var, h);
        } while (expr.eval(nametable, functiontable, var, h).value() > 0);

    }
}

//added for 2c
class ParamList {

    private List<String> parameterlist;

    public ParamList(String name) {
        parameterlist = new LinkedList<String>();
        parameterlist.add(name);
    }

    public ParamList(String name, ParamList parlist) {
        parameterlist = parlist.getParamList();
        parameterlist.add(name);
    }

    public List<String> getParamList() {
        return parameterlist;
    }
}

// Added for 2c
class ExpressionList {

    private LinkedList<Expr> list;

    public ExpressionList(Expr ex) {
        list = new LinkedList<Expr>();
        list.add(ex);
    }

    public ExpressionList(Expr ex, ExpressionList el) {
        list = new LinkedList<Expr>();
        //we need ot add the expression to the front of the list
        list.add(0, ex);

    }

    public List<Expr> getExpressions() {
        return list;
    }
}

class StatementList {

    private LinkedList<Statement> statementlist;

    public StatementList(Statement statement) {
        statementlist = new LinkedList<Statement>();
        statementlist.add(statement);
    }
    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) throws Exception {


        for (Statement stmt : statementlist) {
            stmt.eval(nametable, functiontable, var, h);

        }
    }

    public void insert(Statement s) {
        // we need to add it to the front of the list
        statementlist.add(0, s);
    }
}

class Proc {

    private ParamList parameterlist;
    private StatementList stmtlist;

    public Proc(ParamList pl, StatementList sl) {
        parameterlist = pl;
        stmtlist = sl;
    }

    public int apply(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, ExpressionList expressionlist, Heap_ h) {
        //System.out.println("Executing Proceedure");
        HashMap<String, Element> newnametable = new HashMap<String, Element>();

        // bind parameters in new name table
        // we need to get the underlying List structure that the ParamList uses...
        Iterator<String> p = parameterlist.getParamList().iterator();
        Iterator<Expr> e = expressionlist.getExpressions().iterator();

        if (parameterlist.getParamList().size() != expressionlist.getExpressions().size()) {
            System.out.println("Param count does not match");
            System.exit(1);
        }
        while (p.hasNext() && e.hasNext()) {

            // assign the evaluation of the expression to the parameter name.
            newnametable.put(p.next(), e.next().eval(nametable, functiontable, var, h));
        //System.out.println("Loading Nametable for procedure with: "+p+" = "+nametable.get(p));

        }
        // evaluate function body using new name table and 
        // old function table
        // eval statement list and catch return
        //System.out.println("Beginning Proceedure Execution..");
        try {
            stmtlist.eval(newnametable, functiontable, var,h);
        } catch (Exception result) {
            // Note, the result shold contain the proceedure's return value as a String
            //System.out.println("return value = "+result.getMessage());
            return Integer.parseInt(result.getMessage());
        }
        System.out.println("Error:  no return value");
        System.exit(1);
        // need this or the compiler will complain, but should never
        // reach this...
        return 0;
    }
}

class Program {

    private StatementList stmtlist;

    public Program(StatementList list) {
        stmtlist = list;
        //Heap_ h = new Heap_(15, nametable);
        //h.print();
    }

    public void eval(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        try {
            stmtlist.eval(nametable, functiontable, var, h);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }

    public void dump(HashMap<String, Element> nametable, HashMap<String, Proc> functiontable, LinkedList var, Heap_ h) {
        //System.out.println(nametable.values());
        System.out.println("Printing Heap....");
        h.print();
        
        System.out.println("Dumping out all the variables...");
        if (nametable != null) {
            for (String name : nametable.keySet()) {
                   //Prints addresses. i tack on a .value() to print out numbers and .getList() gives me an address
                System.out.println(name + "=" +
                    nametable.get(name).toString());
            }
        }
        if (functiontable != null) {
            for (String name : functiontable.keySet()) {
                System.out.println("Function: " + name + " defined...");
            }
        }
    }
}


